package hash;

/**
 * 基于开散列方案下的哈希表实现
 */

import java.util.NoSuchElementException;

public class MyHashMap {
    private class Node{
        int key;
        int value;
        Node next;

        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    // 当前哈希表中实际存储元素的个数
    private int size;
    // 默认哈希表的长度
    // 有的教科书，将每个哈希表的数组元素称为哈希桶
    private static final int DEFAULT_CAPACITY = 16;
    // 默认负载因子
    private static final double LOAD_FACTOR = 0.75;
    // 取模数，用于取得key的索引
    private int M;
    // 实际存储数据的数组
    private Node[] data;

    public MyHashMap(){
        this(DEFAULT_CAPACITY);
    }
    public MyHashMap(int initCapacity) {
        this.data = new Node[initCapacity];
        this.M = initCapacity;
    }

    public int hash(int key){
        return Math.abs(key) % M;
    }

    // 在当前的哈希表添加一个键值对 key = value
    public int add(int key,int value){
        // 1.先对key取模,得到存储的索引
        int index = hash(key);
        // 2.遍历这个索引对应的链表，查看当前的key是否已经存在了
        for (Node x = data[index];x != null;x = x.next) {
            if (x.key == key) {
                // 此时key已经存在，更新value
                int oldVal = x.value;
                x.value = value;
                return oldVal;
            }
        }
        // 3.此时key对应的元素在当前的哈希表中不存在，新建节点头插哈希表中
        Node newNode = new Node(key,value,data[index]);
        data[index] = newNode;
        size++;

        // 4.添加一个新元素后，查看是否需要扩容
        if(data.length * LOAD_FACTOR > size){
            //扩容
            resize();
        }
        return value;
    }

    /**
     * 删除哈希表中key对应的节点
     * 返回删除前的value
     * @param key
     * @return
     */
    public int removeKey(int key){
        int index = hash(key);
        // 判断头节点是否是待删除的节点
        Node head = data[index];
        if(data[index].key == key){
            int value = head.value;
            data[index] =head.next;
            head.next = head = null;
            size--;
            return value;
        }
        // 当前链表的头节点不是待删除的节点
        Node pre =data[index];
        while (pre.next != null){
            if(pre.next.key == key){
                Node cur = pre.next;
                int value = cur.value;
                pre.next = cur.next;
                cur.next = cur = null;
                size--;
                return value;
            }
            pre = pre.next;
        }
        throw new NoSuchElementException("no such key!remove error!");
    }

    /**
     * 哈希表扩容
     */
    private void resize() {
        // 新数组长度变为原来的一倍
        Node[] newData = new Node[data.length << 1];
        // 原节点的key对应新数组的索引hash
        // 现在的取模数应该变为新数组的长度
        this.M = newData.length;
        // 遍历原数组,进行节点的搬移
        for (int i = 0; i < data.length; i++) {
            if (data[i] != null) {
                // 对应的链表不为空
                // 进行对应的链表遍历
                for (Node x = data[i];x != null;) {
                    // 暂存一下后继节点
                    Node next = x.next;
                    int newIndex = hash(x.key);
                    // 新数组的头插
                    x.next = newData[newIndex];
                    newData[newIndex] = x;
                    // 继续进行下一个节点的搬移操作
                    x = next;
                }
            }else {
                // 当前数组i对应的索引下，没有节点
                continue;
            }
        }
        data = newData;
    }

    public boolean containsKey(int key){
        int index = hash(key);

        // 遍历index位置对应的链表，查看是否有节点的key与查询的key相等
        for(Node x = data[index];x != null;x = x.next ){
            if(key == x.key){
                return true;
            }
        }
        return false;
    }

    public boolean containsValue(int value) {
        // 遍历整个哈希表
        for (int i = 0; i < size; i++) {
            for (Node x = data[i];x != null;x = x.next) {
                if (x.value == value) {
                    return true;
                }
            }
        }
        return false;
    }
}
